package 树.递归;

/*
解题思路：
   这题采用双递归的方式，但是依旧是按照递归的模板来（1.找到最简单的子问题求解，2.其他问题不考虑内在细节，只考虑整体逻辑）。
   题目要求 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点） 。这就要求我们只需要去求三部分即可：
   以当前节点作为头结点的路径数量
   以当前节点的左孩子作为头结点的路径数量
   以当前节点的右孩子作为头结点啊路径数量
将这三部分之和作为最后结果即可。

但是注意我们要新写一个辅助方法，用来求上面三种情况的路径，并且在这个辅助函数里面还要调用递归。即：假如现在穿了一个root给辅助函数，因为“不需要在叶子节点结束”，所以每隔一个节点都要判断一次这一个节点的值满不满足要求，也就是sum-root.val是否为0.如果是结果路径+1，然后   “不管上一步的路径是否加1”我们都要去找root的左子树 ，右子树，即“找到一个节点要做的事，剩下的交给递归框架”
*/
public class 路径总和III_437 {
    public boolean isSubtree(TreeNode s, TreeNode t) {

        if (t == null) return true;   // t 为 null 一定都是 true:空树为任何树的子树
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false


        boolean rootFlag = help(s, t);//s也是s的子树，看s这颗子树是否在t中有相同结构的子树


        boolean leftFlag = isSubtree(s.left, t);
        boolean rightFlag = isSubtree(s.right, t);

        return leftFlag || rightFlag || rootFlag;//只要s这一整棵树中， 有一种子树在t中有相同结构的子树，就应该返回true。
    }


    public boolean help(TreeNode s, TreeNode t) {//判断两棵树是否相同
        //base case
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;

        //一个节点要做的事情
        if (s.val != t.val) return false;

        boolean leftFlag = help(s.left, t.left);
        boolean rightFlag = help(s.right, t.right);

        return leftFlag && rightFlag;//因为是要求“具有相同结构和节点值”，所以必须要左子树返回的值为true，右子树返回的值也为true，即该节点，该节点的左子树，该节点的右子树（他们仨合起来称成为了一颗完整的s的子树），都可以在t中找到相同结构的子树。

    }
}
